﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace Mesuro.Equation {
	public class EqParser {

		public static char RADIX_POINT = '.';

		public static EqTerm Parse( String expression ) {
			EqTerm current = null;
			List<EqTerm> termList = new List<EqTerm>();
			Stack<List<EqTerm>> parenStack = new Stack<List<EqTerm>>();
			StringBuilder buffer = new StringBuilder();
			int i = 0;
			char c = '\0';

			while (i < expression.Length) {
				buffer.Clear();

				//Try parse as constant
				_extractConstant( ref buffer, ref expression, ref i );
				if (buffer.Length > 0) {
					//A Constant was found
					current = EqConstant.Parse( buffer.ToString() );
					buffer.Clear();
					//handle implicit operations
					_addImplicitIfNecessary( ref termList, current );
					//Add constant to term list
					termList.Add( current );
					current = null;

					continue;
				}

				//Try parse as symbol
				while (i < expression.Length && _symbolCanContain( c = expression[i] )) {
					buffer.Append( c );
					i++;
				}
				if (buffer.Length > 0 && (EqOperatorDefinition.FindOperators( buffer.ToString() ).Count == 0)) {
					//A symbol has been found
					current = new EqSymbolInstance( buffer.ToString() );
					buffer.Clear();

					_addImplicitIfNecessary( ref termList, current );

					termList.Add( current );
					current = null;

					continue;
				}

				while (i < expression.Length && _operatorStartsWith( buffer.ToString() + (c = expression[i]) )) {
					buffer.Append( c );
					i++;
				}
				if (buffer.Length > 0) {
					//An operator has been found

					//Spaces should be ignored
					if (buffer.ToString().Equals( " " )) continue;

					current = new EqProtoOperator( buffer.ToString() );
					buffer.Clear();

					_addImplicitIfNecessary( ref termList, current );

					termList.Add( current );
					current = null;

					continue;
				}

				if (Char.IsWhiteSpace( c )) {
					i++;
					continue;
				}

				if (c == '(') {
					parenStack.Push( termList );
					termList = new List<EqTerm>();
					i++;
					continue;
				} else if (c == ')') {
					current = ConstructExpressionTree( termList );
					termList = parenStack.Pop();
					EqSymbolInstance func = (termList.Count > 0) ? termList[termList.Count - 1] as EqSymbolInstance : null;
					if (func != null)
						func.Argument = current;
					else {
						_addImplicitIfNecessary( ref termList, current );
						termList.Add( current );
					}
					i++;
					continue;
				}
				throw new MalformedExpressionException( String.Format( "Unable to parse expression at character {0}: {1}", i, c ) );
			}
			current = ConstructExpressionTree( termList );
			return current;
		}

		public static EqTerm Evaluate( String expression, EqScope scope = null ) {
			if (scope == null) scope = EqScope.Default;
			return Parse( expression ).Evaluate( scope );
		}

		#region Utility Methods
		private static void _extractConstant( ref StringBuilder buffer, ref string expression, ref int i ) {
			bool pointFound = false;
			char c = '\0';
			do {
				while (i < expression.Length && Char.IsDigit( c = expression[i] )) {
					buffer.Append( c );
					i++;
				}
				if (c == RADIX_POINT && !pointFound) {
					buffer.Append( c );
					pointFound = true;
					i++;
				} else
					break;
			} while (true);
		}

		private static bool _operatorStartsWith( string p ) {
			return EqOperatorDefinition.AnyOperatorsStartWith( p );
		}

		private static bool _symbolCanContain( char p ) {
			return Char.IsLetter( p ) || p == '_';
		}

		private static void _addImplicitIfNecessary( ref List<EqTerm> termList, EqTerm current ) {
			if (termList.Count == 0) return;
			if (termList[termList.Count - 1] is EqProtoOperator || current is EqProtoOperator)
				return;
			termList.Add( new EqProtoOperator( " " ) );
		}

		private static EqTerm ConstructExpressionTree( List<EqTerm> termList ) {
			int highestIndx = -1;
			int highestPrec = -1;
			EqProtoOperator pro;
			while (termList.Count > 1) {

				//Find highest precedence operator
				//Start from right so as to evaluate in RTL fashion
				for (int i = termList.Count-1; i > -1 ; i--)
					if ((pro = termList[i] as EqProtoOperator) != null)
						if (pro.Precedence > highestPrec) { highestPrec = pro.Precedence; highestIndx = i; }

				//If there was an operator, make it a node
				if (highestIndx != -1)
					ConstructExpressionNodeAt( ref termList, ref highestIndx );

				else { //There were no operators, handle implicit multiplication
					while (termList.Count > 1) {

						highestIndx = 1;//Insert point

						//Insert a multiplication protoOperator
						termList.Insert( highestIndx, new EqProtoOperator( " " ) );

						//construct the operator
						_createBinaryOperator( ref termList, ref highestIndx );
					}
				}

				highestIndx = -1;
				highestPrec = -1;
			}

			return termList[0];
		}

		private static void ConstructExpressionNodeAt( ref List<EqTerm> termList, ref int cIndex ) {
			EqTerm cur = termList[cIndex];
			if (cur is EqConstant || cur is EqSymbolInstance)
				return;

			EqProtoOperator oCur = (EqProtoOperator)cur; //We already know this is EqProtoOperator instance
			EqProtoOperator oPrev = (cIndex > 0) ? termList[cIndex - 1] as EqProtoOperator : null; //These might not be EqProtoOperator instances
			EqProtoOperator oNext = (cIndex < termList.Count - 1) ? termList[cIndex + 1] as EqProtoOperator : null;

			bool tryAgain = false;

			if (cIndex == 0 && oCur.Arguments.HasFlag( EqOperatorArguments.LHS )) {
				if (!oCur.Select( EqOperatorArguments.PREFIX ))
					if (!oCur.Select( EqOperatorArguments.SINGLE ))
						throw new MalformedExpressionException( "Cannot start an expression with " + oCur.Definition.Key );
			}

			if (oPrev == null && oNext == null) {//Single operator
				switch (oCur.Arguments) {
					case EqOperatorArguments.SINGLE:
						_createSingleOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.PREFIX:
						_createPrefixOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.SUFFIX:
						_createSuffixOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.BINARY:
						_createBinaryOperator( ref termList, ref cIndex );
						break;
				}
			} else if (oNext == null) {//Double operator
				switch (oCur.Arguments) {
					case EqOperatorArguments.SINGLE:
						_createSingleOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.PREFIX:
						_createPrefixOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.SUFFIX:
						if (oPrev.Arguments.HasFlag( EqOperatorArguments.RHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createSuffixOperator( ref termList, ref cIndex );
						break;

					case EqOperatorArguments.BINARY:
						if (oPrev.Arguments.HasFlag( EqOperatorArguments.RHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createBinaryOperator( ref termList, ref cIndex );
						break;
				}
			} else if (oPrev == null) {//Double operator
				switch (oCur.Arguments) {
					case EqOperatorArguments.SINGLE:
						_createSingleOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.PREFIX:
						if (oNext.Arguments.HasFlag( EqOperatorArguments.LHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createPrefixOperator( ref termList, ref cIndex );
						break;

					case EqOperatorArguments.SUFFIX:
						_createSuffixOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.BINARY:
						if (oNext.Arguments.HasFlag( EqOperatorArguments.LHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createBinaryOperator( ref termList, ref cIndex );
						break;
				}
			} else {//Triple operator
				switch (oCur.Arguments) {
					case EqOperatorArguments.SINGLE:
						_createSingleOperator( ref termList, ref cIndex );
						break;
					case EqOperatorArguments.PREFIX:
						if (oNext.Arguments.HasFlag( EqOperatorArguments.LHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createPrefixOperator( ref termList, ref cIndex );
						break;

					case EqOperatorArguments.SUFFIX:
						if (oPrev.Arguments.HasFlag( EqOperatorArguments.RHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createSuffixOperator( ref termList, ref cIndex );
						break;

					case EqOperatorArguments.BINARY:
						if (oPrev.Arguments.HasFlag( EqOperatorArguments.RHS ) || oNext.Arguments.HasFlag( EqOperatorArguments.LHS ))
							tryAgain = _tryResolveOperators( ref oPrev, ref oCur, ref oNext );
						else
							_createBinaryOperator( ref termList, ref cIndex );
						break;
				}
			}
		}

		private static EqOperatorInstance _createSingleOperator( ref List<EqTerm> termList, ref int cIndex ) {

			EqProtoOperator oCur = termList[cIndex] as EqProtoOperator;
			if (oCur == null) throw new ArgumentException( "termList[cIndex] was not an EqProtoOperator" );
			EqOperatorInstance op = new EqOperatorInstance( oCur.Definition );

			termList[cIndex] = op;
			return op;
		}

		private static EqOperatorInstance _createPrefixOperator( ref List<EqTerm> termList, ref int cIndex ) {

			EqProtoOperator oCur = termList[cIndex] as EqProtoOperator;
			if (oCur == null) throw new ArgumentException( "termList[cIndex] was not an EqProtoOperator" );
			EqOperatorInstance op = new EqOperatorInstance( oCur.Definition );

			op.RHS = termList[cIndex + 1];
			termList.RemoveAt( cIndex + 1 );

			termList[cIndex] = op;
			return op;
		}

		private static EqOperatorInstance _createSuffixOperator( ref List<EqTerm> termList, ref int cIndex ) {

			EqProtoOperator oCur = termList[cIndex] as EqProtoOperator;
			if (oCur == null) throw new ArgumentException( "termList[cIndex] was not an EqProtoOperator" );
			EqOperatorInstance op = new EqOperatorInstance( oCur.Definition );

			op.LHS = termList[cIndex - 1];
			termList.RemoveAt( --cIndex );

			termList[cIndex] = op;
			return op;
		}

		private static EqOperatorInstance _createBinaryOperator( ref List<EqTerm> termList, ref int cIndex ) {

			EqProtoOperator oCur = termList[cIndex] as EqProtoOperator;
			if (oCur == null) throw new ArgumentException( "termList[cIndex] was not an EqProtoOperator" );
			EqOperatorInstance op = new EqOperatorInstance( oCur.Definition );

			op.LHS = termList[cIndex - 1];
			termList.RemoveAt( --cIndex );

			op.RHS = termList[cIndex + 1];
			termList.RemoveAt( cIndex + 1 );

			termList[cIndex] = op;
			return op;
		}

		private static bool _tryResolveOperators( ref EqProtoOperator oPrev, ref EqProtoOperator oCur, ref EqProtoOperator oNext ) {
			if (oNext == null && oPrev == null)
				throw new InvalidProgramException( "No resolution is needed. Why are we here?" );

			if (oNext == null)
				switch (oCur.Arguments) {
					case EqOperatorArguments.BINARY:
					case EqOperatorArguments.SUFFIX:
						if (oPrev.Select( EqOperatorArguments.SUFFIX ))
							return true;
						if (oPrev.Select( EqOperatorArguments.SINGLE ))
							return true;
						if (!oCur.SelectNext())
							throw new MalformedExpressionException( "Cannot resolve operator sequence: " + oCur.Definition.Key + oNext.Definition.Key );
						return true;
					case EqOperatorArguments.PREFIX:
					case EqOperatorArguments.SINGLE:
						throw new InvalidProgramException( "No resolution is needed. Why are we here?" );
				}

			if (oPrev == null)
				switch (oCur.Arguments) {
					case EqOperatorArguments.BINARY:
					case EqOperatorArguments.PREFIX:
						if (oNext.Select( EqOperatorArguments.PREFIX ))
							return true;
						if (oNext.Select( EqOperatorArguments.SINGLE ))
							return true;
						if (!oCur.SelectNext())
							throw new MalformedExpressionException( "Cannot resolve operator sequence: " + oCur.Definition.Key + oNext.Definition.Key );
						return true;
					case EqOperatorArguments.SUFFIX:
					case EqOperatorArguments.SINGLE:
						throw new InvalidProgramException( "No resolution is needed. Why are we here?" );
				}

			//Triple operator...
			switch (oCur.Arguments) {
				case EqOperatorArguments.BINARY:
					if (oNext.Select( EqOperatorArguments.SUFFIX ) && oPrev.Select( EqOperatorArguments.PREFIX ))
						return true;
					if (oNext.Select( EqOperatorArguments.SUFFIX ) && oPrev.Select( EqOperatorArguments.SINGLE ))
						return true;
					if (oNext.Select( EqOperatorArguments.SINGLE ) && oPrev.Select( EqOperatorArguments.PREFIX ))
						return true;
					if (oNext.Select( EqOperatorArguments.SINGLE ) && oPrev.Select( EqOperatorArguments.SINGLE ))
						return true;
					if (!oCur.SelectNext())
						throw new MalformedExpressionException( "Cannot resolve operator sequence: " + oCur.Definition.Key + oNext.Definition.Key );
					return true;
				case EqOperatorArguments.PREFIX:
					if (oNext.Select( EqOperatorArguments.PREFIX ))
						return true;
					if (oNext.Select( EqOperatorArguments.SINGLE ))
						return true;
					if (!oCur.SelectNext())
						throw new MalformedExpressionException( "Cannot resolve operator sequence: " + oCur.Definition.Key + oNext.Definition.Key );
					return true;
				case EqOperatorArguments.SUFFIX:
					if (oPrev.Select( EqOperatorArguments.SUFFIX ))
						return true;
					if (oPrev.Select( EqOperatorArguments.SINGLE ))
						return true;
					if (!oCur.SelectNext())
						throw new MalformedExpressionException( "Cannot resolve operator sequence: " + oCur.Definition.Key + oNext.Definition.Key );
					return true;
				default:
					throw new InvalidProgramException( "Shouldn't exist" );
			}

		}
		#endregion
	}

	public class EqExpressionBuilder : EqParser {

		private List<EqTerm> termList;
		private EqTerm current;
		private StringBuilder buffer;

		private StringBuilder _expression;
		public StringBuilder Expression {
			get { return _expression; }
			set { _expression = value; }
		}

		//public void Append( String str );
		//public void Insert( int pos, String str );
	}
}
